Lambda the Ultimate

Ehud, theoretically on vacation, emailed me a link to an article from the June ACM Queue, Syntactic Heroin:

User-defined overloading is a syntactic drug that has seduced all too many language designers, programmers, and project managers.

It's focused on overloading in C++, and in particular the problems that can arise with implicit conversions, both built-in and programmer-defined. The author concludes that this is all a very bad idea, although to my disappointment, he doesn't explore more disciplined approaches to "overloading" in languages that are less conversion-happy, such as parameterized higher-order modules in functional languages, or Haskell's typeclasses.

Trampolining Architectures

A trampolining architecture is a special case and extension of a monad which is useful in implementing multiprogramming. Five trampolining architectures, operating over the range of two trampolining translations, are presented. The effects of the architectures are cumulative. Some increase the breadth of multiprogramming facilities provided. Others demonstrate the potential for more efficient implementation. Finally, we demonstrate the applicability of trampolining to languages without closures.

We discussed more than once Trampolined Style, but never this paper by the same authors (except Wand). Published one year later, it discusses more options, and more importantly, shows relations between trampolines and monads.

If you are interested in design and implementation of PLs, and you never heard about tramplines - you should.

Causal Nets

The network approach to computation is more direct and "physical" than the one based on some specific computing devices (like Turing machines). However, the size of a usual -- e.g., Boolean -- network does not reflect the complexity of computing the corresponding function, since a small network may be very hard to find even if it exists. A history of the work of a particular computing device can be described as a network satisfying some restrictions. The size of this network reflects the complexity of the problem, but the restrictions are usually somewhat arbitrary and even awkward. Causal nets are restricted only by determinism (causality) and locality of interaction. Their geometrical characteristics do reflect computational complexities. And various imaginary computer devices are easy to express in their terms. The elementarity of this concept may help bringing geometrical and algebraic (and maybe even physical) methods into the theory of computations. This hope is supported by the grouptheoretical criterion given in this paper for computability from symmetrical initial configurations.

The nets of this paper are different from belief nets or Bayesian nets, which are also known under name "causal nets".

No doubt, modeling the history of computation rather than the current state is nothing new, but this paper tries to find new applications for that.

For once, a story from Kuro5hin.

Formal Specification helps build more robust, more maintainable software with fewer bugs and defects. It has a long history, but it is still a developing field. While it may not be suitable for all software projects, a case can be made that there are many projects not currently using formal specification that stand to benefit from it. As the methods and tools for formal specification develop it is increasingly becoming something that developers and software engineers should learn to use to their advantage.

I haven't had a chance to read it yet, but this story mentions SPARK and CASL, and seems reasonably well-researched.

Programming Paradigms of the Andorra Kernel Language

The Andorra Kernel Language (AKL) is introduced. It is shown how AKL provides the programming paradigms of both Prolog and GHC. This is the original goal of the design. However, it has also been possible to provide capabilities beyond that of Prolog and GHC. There are means to structure search, more powerful than plain backtracking. It is possible to encapsulate search in concurrent reactive processes. It is also possible to write a multi-way merger with constant delay. In these respects AKL is quite original. Although AKL is an instance of our previously introduced Kernel Andorra Prolog framework, this exposition contains important extensions, and a considerable amount of unnecessary formal overhead has been stripped away.

That's the AKL that is a predecessor of Oz (and was codeveloped by a coauthor of CTM, Seif Haridi).

While not the latest word in its area (published in 1991), it is well worth reading (and I don't remember seeing links to it on LtU).

I am going on vacation, and will not be able to post or read LtU regularly until Aug. 25 .

I am sure the rest of the team will keep things in order until I get back. Play nice...

Nils Anders Danielsson, Jeremy Gibbons, John Hughes and Patrik Jansson (2005). Fast and Loose Reasoning is Morally Correct.

We justify reasoning about non-total (partial) functional languages using methods seemingly only valid for total ones; this permits "fast and loose" reasoning without actually being loose...

Functional languages satisfy many pleasing equational laws, such as curry o uncurry = id, (fst x, snd x) = x and fst(x,y) = x and many others inspired by category theory. Such laws can be used to perform very pleasant proofs of program equality... There is just one problem. In real programming languages such as Haskell and ML, they do not hold.

However, not to worry: The authors show that if two closed terms have the same semantics for total functions, they have related semantics for partial functions.

ACM SIGPLAN has given the 2005 Programming Languages Achievement Award to Erich Gamma, Richard Helm, Ralph Johnson and John Vlissides, authors of Design Patterns.

In this Interview, Date discusses his new book, Database in Depth: Relational Theory for Practitioners. The book does look interesting and is on my list to be acquired at some point in the future. The Third Manifesto crowd can be a bit bellicose at times (at least for my tastes), but I can't say that I disagree with many of their assessments.

The underlying model (relational in this case) is of interest but more importantly is the manner in which it manifests itself within the language chosen for communication. SQL has some advantages as a language that I think extend beyond the realm of being ubiquitous. It primarily serves as a bridge between the programming languages that we choose, and the databases that we are stuck with. One could naturally ask the question of why have a seperate language in the first place (Object Databases tend to go this route)? And why do we need either SQL or D, when we have much more universal programming languages available at our disposal? If one surmizes that a database language is needed but that it should somehow be crippled in expressiveness (e.g. not turing complete, not imperative, not....), then one is forced to answer the question of where to draw the line.

That said, what I am currently wondering is if there is an implementation of the D language besides Dataphor? I guess I'm spoiled by the myriad of unencumbered programming languages that are being actively developed and I sometimes think that there is a cultural divide between those who implement programming languages and those that work with languages in the database market. Perhaps what we need is for an unassuming brilliance to appear out of seemingly nowhere and surprise us with an implementation of the language in Haskell or Scheme. Any more Autrijus' out there? :-)

The website of Hutton's introductory Programming in Haskell book, now includes eleven powerpoint presentations covering most of the chapters in the book. Each set of slides is intended to be used for a one hour lecture.